package main.leetcode.clockin.September;

import main.datastruc.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 94. 二叉树的中序遍历 给定一个二叉树，返回它的中序 遍历。
 *
 * <p>示例: <br>
 * 输入: [1,null,2,3] 1 \ 2 / 3<br>
 * 输出: [1,3,2]
 *
 * <p>进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 */
public class day14 {
    public static void main(String[] args) {
        System.out.println(
                new day14().inorderTraversal(TreeNode.creCmpBTree(new int[] {1, 2, 3, 4, 5})));
    }

    /** 迭代 */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            // 左路全部压入栈
            while (node != null) {
                stack.offerLast(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                node = stack.pollLast();
                res.add(node.val);
                // 转入右路，相当于开启下一轮迭代
                node = node.right;
            }
        }
        return res;
    }

    //    /** 递归 */
    //    private List<Integer> res = new ArrayList<>();
    //
    //    public List<Integer> inorderTraversal(TreeNode root) {
    //        if (root != null) {
    //            inorderTraversal(root.left);
    //            res.add(root.val);
    //            inorderTraversal(root.right);
    //        }
    //        return res;
    //    }
}
